package algorithm.personal.combinationpermutation;

import cn.hutool.core.convert.Convert;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Stream;

import static algorithm.personal.combinationpermutation.Combination.combinationSize;

public class Base {
//    java.lang.StackOverflowError
//    public static int factorial(int n) {
//        if(0 == n || 1 == n){
//            return 1;
//        }else{
//            return n * factorial(n - 1);
//        }
//    }

    /**
     * 计算n的阶乘
     * @param n
     * @return
     */
    public static int factorial(int n) {
        int result = 1;
        if(0 != n && 1 != n){
            for (int i = 1; i < n; i++) {
                result *= i + 1;
            }
        }
        return result;
    }



//    计算一个数组的组合（排列组合中的组合）
    public static List<int[]> nchoosek(int[] array, int k){
        int n = array.length;
        checknk(n, k);
        List<int[]> combList = new ArrayList<>(nchoosek(n, k > (n - k) ? n - k : k));
        nchoosek0(array, n, new int[k], k, 0, 0, combList);
        return combList;
    }

    private static void nchoosek0(int[] array, int n, int[] comb, int k,
                                  int aIndex, int cIndex, List<int[]> combList){
        if(cIndex == k){
            combList.add(Arrays.copyOf(comb, k));
            return;
        }
        for(int i = aIndex, limit = n - (k - cIndex); i <= limit; i++){
            comb[cIndex++] = array[i];
            nchoosek0(array, n, comb, k, i + 1, cIndex, combList);
            cIndex--;
        }
    }
    public static void checknk(int n, int k){
        if(k < 0 || k > n){ // N must be a positive integer.
            throw new IllegalArgumentException("K must be an integer between 0 and N.");
        }
    }
    public static int nchoosek(int n, int k){
        checknk(n, k);
        k = (k > (n - k)) ? n - k : k;  // C(n, k) = C(n, n - k)
        if(k <= 1){  // C(n, 0) = 1, C(n, 1) = n
            return k == 0 ? 1 : n;
        }
        int divisor = n - k + 1;
        int dividend = 1;
        double cnk = 1.0;
        for(int i = 0; i < n; i++){
            cnk *= (double) (divisor + i) / (dividend + i);
        }
        return (int) cnk;
    }


    public static void main(String[] args) {
        calculateStringArray();
    }

    //    计算一个整形数组组合的例子
    public static void calculateIntArray() {
        int[] array = {1,2,3,4,5};
        int k = 3;
        List<int[]> result = nchoosek(array,k);
        for (int i = 0; i < result.size(); i++) {
            for (int j = 0; j < k; j++) {
                if(j == 0){
                    System.out.print(i + 1);
                    System.out.printf("[");
                }
                System.out.print(result.get(i)[j]);
                if(j != k - 1){
                    System.out.printf(",");
                }
                if(j == k - 1){
                    System.out.printf("]");
                }
            }
            System.out.println();
        }

        System.out.println(combinationSize(3,5));
    }
/*
[1,2,3]
[1,2,4]
[1,2,5]
[1,3,4]
[1,3,5]
[1,4,5]
[2,3,4]
[2,3,5]
[2,4,5]
[3,4,5]
* */

    //    字符串数组
    public static void calculateStringArray() {
        String[] strings = {"1","2","3","4","5"};
        Integer[] array = Convert.toIntArray(strings);
//        int[] ints = Arrays.stream(array).mapToInt(Integer::valueOf).toArray();
        int[] ints = Arrays.stream(array).mapToInt(e ->Integer.valueOf(e)).toArray();




        int k = 3;
        List<int[]> result = nchoosek(ints,k);

        Stream.of(result).forEach(e -> System.out.print("第" + "个" + "[" + e + "," + "]"));

//        for (int i = 0; i < result.size(); i++) {
//            for (int j = 0; j < k; j++) {
//                if(j == 0){
//                    System.out.print(i + 1);
//                    System.out.printf("[");
//                }
//                System.out.print(result.get(i)[j]);
//                if(j != k - 1){
//                    System.out.printf(",");
//                }
//                if(j == k - 1){
//                    System.out.printf("]");
//                }
//            }
//            System.out.println();
//        }

        System.out.println(combinationSize(3,5));

    }



}
